<?php
/**
 * User: LRZ
 * Date: 2020/2/25
 * Time: 10:37
 */

$res0 = sort0([5, 8, 6, 3, 9, 2, 1, 7]);
print_r($res0);

/**
 * 冒泡排序
 * @param $array
 * @return mixed
 */
function sort0($array)
{
    $size = count($array);
    for ($i = 0; $i < $size - 1; $i++) {
        for ($j = 0; $j < $size - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $tmp           = $array[$j];
                $array[$j]     = $array[$j + 1];
                $array[$j + 1] = $tmp;
            }
        }
    }
    return $array;
}

/**
 * 冒泡排序 - 优化 I
 * @param $array
 * @return mixed
 */
function sort1($array)
{
    $size = count($array);
    for ($i = 0; $i < $size - 1; $i++) {
        // 有序标记，每一轮都是true
        $isSorted = true;
        for ($j = 0; $j < $size - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $tmp           = $array[$j];
                $array[$j]     = $array[$j + 1];
                $array[$j + 1] = $tmp;
                // 当发生元素交换时，标记改为false
                $isSorted = false;
            }
        }
        // 如果标记为true，说明数组为有序数组，直接退出循环
        if ($isSorted) {
            break;
        }
    }
    return $array;
}

/**
 * 冒泡排序 - 优化 II
 * @param $array
 * @return mixed
 */
function sort2($array)
{
    $size       = count($array);
    $sortBorder = $size - 1;
    $pos        = 0;
    for ($i = 0; $i < $size - 1; $i++) {
        $isSorted = true;
        // 优化循环条件，把循环的终止条件改为无序数列的边界
        for ($j = 0; $j < $sortBorder; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $tmp           = $array[$j];
                $array[$j]     = $array[$j + 1];
                $array[$j + 1] = $tmp;
                $isSorted      = false;
                // 把无序数列的边界更新为最后一次交换元素的位置
                $pos = $j;
            }
        }
        if ($isSorted) {
            break;
        }
        $sortBorder = $pos;
    }
    return $array;
}

/**
 * 冒泡排序 - 优化 III
 * @param $array
 * @return mixed
 */
function sort3($array)
{
    $size       = count($array);
    $sortBorder = $size - 1;
    $pos        = 0;
    for ($i = 0; $i < $size - 1; $i++) {
        $isSorted = true;
        // 正向寻找最大值
        for ($j = $i; $j < $sortBorder; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $tmp           = $array[$j];
                $array[$j]     = $array[$j + 1];
                $array[$j + 1] = $tmp;
                $isSorted      = false;
                $pos           = $j;
            }
        }
        if ($isSorted) {
            break;
        }
        // 无序序列的边界
        $sortBorder = $pos;

        // 反向寻找最小值。从无序数列的边界开始反向循环。
        for ($j = $sortBorder; $j > $i; $j--) {
            if ($array[$j] < $array[$j - 1]) {
                $tmp           = $array[$j];
                $array[$j]     = $array[$j - 1];
                $array[$j - 1] = $tmp;
                $isSorted      = false;
            }
        }
        if ($isSorted) {
            break;
        }
    }
    return $array;
}